//
// Description: 300. 最长递增子序列
// Created by Loading on 2021/7/31.
//

#include <bits/stdc++.h>

using namespace std;

/* 贪心 + 二分 ，时间复杂度：O(nlogn) */
int lengthOfLIS(vector<int> &nums) {
    vector<int> maxLen_increase;

    for (auto &x : nums) {
        auto it = lower_bound(maxLen_increase.begin(), maxLen_increase.end(), x);
        if (it != maxLen_increase.end()) {
            *it = x;
        } else {
            maxLen_increase.emplace_back(x);
        }
    }

    return (int) maxLen_increase.size();
}

/* 动态规划 ，时间复杂度：O(n2) */
int lengthOfLIS_DP(vector<int> &nums) {
    // dp数组，dp[i] 表示以 i 结尾的最长递增子序列长度
    vector<int> dp(nums.size());

    for (int i = 0; i < nums.size(); ++i) {
        dp[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    vector<int> nums1 = {0, 1, 0, 3, 2, 3};
    vector<int> nums2 = {7, 7, 7, 7, 7, 7, 7};

    cout << lengthOfLIS(nums) << endl;
    cout << lengthOfLIS(nums1) << endl;
    cout << lengthOfLIS(nums2) << endl;

    cout << lengthOfLIS_DP(nums) << endl;
    cout << lengthOfLIS_DP(nums1) << endl;
    cout << lengthOfLIS_DP(nums2) << endl;
}